package recursion

import org.scalatest.{FunSpec, Matchers}

/**
 * Given a linked list, swap every two adjacent nodes and return its head.
 * Given 1->2->3->4, you should return the list as 2->1->4->3.
 */
class Q24SwapNodesInPair extends FunSpec with Matchers {

  def swapPairs(head: ListNode): ListNode = {
    if (head == null || head.next == null) head
    else {
      val s1 = head.next
      val t = s1.next
      s1.next = head
      head.next = swapPairs(t)
      s1
    }
  }

  describe("reverse linked list") {
    it("recursive") {
      val a1 = new ListNode(1)
      val a2 = new ListNode(2)
      val a3 = new ListNode(3)
      val a4 = new ListNode(4)
      a1.next = a2
      a2.next = a3
      a3.next = a4

      println(s"result: ${swapPairs(a1)}")
    }
  }

}